package 力扣面试经典150;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-03-02
 * Time:19:48
 */

/**
 * 力扣面试经典150:42. 接雨水
 * 困难
 * 相关标签
 * 相关企业
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * 示例 1：
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 */
public class trap {
    public static void main(String[] args) {
        System.out.println(trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
    }
//   超出时间限制
//    public static int trap(int[] height) {
//        int sum = 0;
//        int max = getMax(height);//找到最大的高度，以便遍历。
//        for (int i = 1; i <= max; i++) {
//            boolean isStart = false; //标记是否开始更新 temp
//            int temp_sum = 0;
//            for (int j = 0; j < height.length; j++) {
//                if (isStart && height[j] < i) {
//                    temp_sum++;
//                }
//                if (height[j] >= i) {
//                    sum = sum + temp_sum;
//                    temp_sum = 0;
//                    isStart = true;
//                }
//            }
//        }
//        return sum;
//    }
//    private static int getMax(int[] height) {
//        int max = 0;
//        for (int i = 0; i < height.length; i++) {
//            if (height[i] > max) {
//                max = height[i];
//            }
//        }
//        return max;
//    }
//   超出时间限制
//    public static int trap(int[] height) {
//        int water = 0;
//        int len = height.length;
//        for (int i = 0; i < len; i++) {
//            //求左边最高的墙
//            int left = 0;
//            for (int j = i - 1; j >= 0; j--) {
//                if (height[j] > left){
//                    left = height[j];
//                }
//            }
//            //求右边最高的墙
//            int right = 0;
//            for (int j = i + 1; j < len; j++) {
//                if (height[j] > right){
//                    right = height[j];
//                }
//            }
//            int min = Math.min(left,right);
//            if (min > height[i]){
//                water += (min - height[i]);
//            }
//        }
//        return water;
//    }

    /**
     * 动态规划
     * @param height
     * @return
     */
    public static int trap(int[] height) {
        int len = height.length;
        int sum = 0;
        int[] left = new int[len];
        int[] right = new int[len];
        for(int i = 1;i < len - 1;i++){
            left[i] = Math.max(left[i - 1],height[i - 1]);
        }
        for(int i = len - 2;i  >0;i--){
            right[i] = Math.max(right[i + 1],height[i + 1]);
        }
        for(int i = 1;i < len - 1;i++){
            if(height[i] < Math.min(left[i],right[i])){
                sum += Math.min(left[i],right[i]) - height[i];
            }
        }
        return sum;
    }
}
